package _11_整理题目._6_模拟设计._计算器;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/basic-calculator-iii/solution/ni-bo-lan-biao-da-shi-jie-fa-chong-chong-0pr6/
 *
 * 中缀转后缀表达式
 *      需要一个 list 保序结果，一个 stack 保存符号
 *      字符串去空格
 *
 *      for 遍历字符串
 *          如果是数字：逐位计算，添加到 list
 *          如果是左括号：压栈 stack
 *          如果是右括号：弹出 (  ) 之间的值加到 list
 *          其他加减乘除：
 *
 */
public class _05_中缀表达式生成逆波兰表达式 {

    public List<String> getRPN(String s) {
        String str = s.replaceAll(" ", "");
        int n = str.length();

        Stack<String> stack = new Stack<>();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (Character.isDigit(str.charAt(i))) {
                int num = 0;
                while (i < n && Character.isDigit(str.charAt(i))) {
                    num = num  * 10 + (str.charAt(i)-'0');
                    i++;
                }
                i--; // 往回走一步
                list.add(num + "");
            } else if (str.charAt(i) == '(') {
                stack.push("(");
            } else if (str.charAt(i) == ')') {
                // 弹出 ( ) 之间的值加到 list
                while (!stack.isEmpty() && !stack.peek().equals("(")) {
                    list.add(stack.pop());
                }
                // 弹出 "("
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                while (!stack.isEmpty() && !stack.peek().equals("(") && getPri(str.charAt(i)+"") <= getPri(stack.peek())) {
                    list.add(stack.pop());
                }
                stack.push(str.charAt(i)+"");
            }
        }

        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }

    public int getPri(String str) {
        if (str.equals("+") || str.equals("-")) return 1;
        if (str.equals("*") || str.equals("/")) return 2;
        return -1;
    }

    @Test
    public void main() {
        String s = "4 - 5 + 3";
        List<String> rpn = getRPN(s);
        System.out.println(rpn);
    }
}
